/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package alloytoy;

/**
 * Computes and saves the transitive closure of a directed graph.
 * @author Daniel
 */
public class TransitiveClosure {
    private boolean[][] tc;
    public TransitiveClosure(Digraph G) {
        tc = new boolean[G.V][G.V];
        for (int v = 0; v < G.V; v++)
            dfs(G, v, v);
	}
	// reachability from s, made it to v
	private void dfs(Digraph G, int s, int v) {
            tc[s][v] = true;
            for (int w : G.adj(v))
                if (!tc[s][w]) dfs(G, s, w);
	}

	public boolean reachable(int v, int w) { return tc[v][w]; }
}
